class MGraph {
    /*图的邻接矩阵表示*/
    int vexs;  //图中结点数目
    String data[];  //存放结点数据
    int [][]weight;  //存放边
    public MGraph(int ve){
        vexs=ve;
        data=new String[ve];
        weight=new int[ve][ve];
    }
}

public class MinTree {

    /*创建图的邻接矩阵*/
    public void CreateGraph(MGraph graph,int vexs,String data[],int [][]weight){
        int i,j;
        for(i=0;i<vexs;i++){
            graph.data[i]=data[i];
            for(j=0;j<vexs;j++){
                graph.weight[i][j]=weight[i][j];
            }
        }
    }

    public void Prim(MGraph graph,int v){
        /*graph为图的邻接矩阵表示，v为起始顶点*/
        int visited[]=new int[graph.vexs];  // visited[]标记结点是否被访问过
        for(int i=0;i<graph.vexs;i++){   //初始化visited[]
            visited[i]=0;
        }

        visited[v]=1;
        int h1=-1,h2=-1;   //记录边的弧尾和弧头
        int minweight=10000;//minweight记录最小权重
        for(int k=1;k<graph.vexs;k++){  //vexs个顶点，最小生成树中有vexs-1条边

            for(int i=0;i<graph.vexs;i++){  //i顶点表示被访问过的顶点
                for(int j=0;j<graph.vexs;j++){  // j顶点表示未被访问过的顶点
                    if(visited[i]==1 && visited[j]==0 && graph.weight[i][j]<minweight){
                        //寻找已访问的顶点与未访问的定点间的权值最小的边
                        minweight=graph.weight[i][j];
                        h1=i;
                        h2=j;
                    }
                }
            }

            System.out.println("边<"+graph.data[h1]+","+graph.data[h2]+"> 距离："+minweight);
            visited[h2]=1;   //标记h2被访问过
            minweight=10000;
        }

    }

    public static void main(String args[]){
        String []data=new String[]{"A村","B村","C村","D村","E村","F村"};
        int vexs=data.length;
        int [][]weight=new int[][]{
                {10000,3,10000,10000,5,6},
                {3,10000,1,10000,10000,4},
                {10000,1,10000,10000,10000,4},
                {10000,10000,6,10000,8,5},
                {6,10000,10000,8,10000,2},
                {5,4,4,5,2,10000}
        };

        MGraph graph=new MGraph(vexs);
        MinTree mt=new MinTree();
        mt.CreateGraph(graph,vexs,data,weight);
        mt.Prim(graph, 0);
    }

}